package week7th.jsjf;

import java.util.*;

import jdk.nashorn.api.tree.Tree;
import week3rd.LinkedQueue;
import week4th.jsjf.ArrayUnorderedList;
import week7th.jsjf.exceptions.ElementNotFoundException;
import week7th.jsjf.exceptions.EmptyCollectionException;

public class LinkedBinaryTree<T> implements BinaryTreeADT<T>, Iterable<T>
{
    public BinaryTreeNode<T> root;
    protected int modCount;
    private LinkedBinaryTree<T> left, right;

    public LinkedBinaryTree() {
        root = null;
    }

    public LinkedBinaryTree(T element) 
    {
        root = new BinaryTreeNode<T>(element);
    }

    public LinkedBinaryTree(T element, LinkedBinaryTree<T> left, 
                            LinkedBinaryTree<T> right) 
    {
        root = new BinaryTreeNode<T>(element);
        root.setLeft(left.root);
        root.setRight(right.root);
        this.left = left;
        this.right = right;
    }

    public void removeRightSubtree() {
        root.setRight(null);
    }

    public void removeLeftSubtree() {
        root.setLeft(null);
    }

    public void removeAllElement() {
        root = null;
    }

    public T getRootElement() throws EmptyCollectionException {
        return root.element;
    }

    protected BinaryTreeNode<T> getRootNode() throws EmptyCollectionException {
        return root;
    }

    public LinkedBinaryTree<T> getLeft() throws ElementNotFoundException
    {
        if (root == null)
            throw new ElementNotFoundException("没有左结点.");

        return left;
    }

    public LinkedBinaryTree<T> getRight()
    {
        if (root == null)
            throw new ElementNotFoundException("没有右结点.");

        return right;
    }

    public boolean isEmpty() 
    {
        return (root == null);
    }

    public int size() {
        int size = 0;
        if(root.getLeft() != null)
            size++;
        if(root.getRight() != null)
            size++;
        return size;

    }

    public int numLeaf() {
        return countLeaf(root);
    }

    public int countLeaf(BinaryTreeNode<T> node) {

        if (node == null)
            return 0;

        if (node.getRight() == null && node.getLeft() == null)
            return 1;

        if (node.getLeft() != null || node.getRight() != null)
            return countLeaf(node.left) + countLeaf(node.right);

        return 0;
    }

    public  int getHeight() {
        return height(this.root);
    }

    private int height(BinaryTreeNode<T> node) {
        if (node == null) {
            return 0;
        }else {
            int left = height(node.getLeft());
            int right = height(node.getRight());
            return left > right ? left + 1 : right + 1;
        }
    }

    public boolean contains(T targetElement) 
    {
        return targetElement == find(targetElement);
    }

    public T find(T targetElement) throws ElementNotFoundException
    {
        BinaryTreeNode<T> current = findNode(targetElement, root);
        
        if (current == null)
            throw new ElementNotFoundException("没有找到指定对象.");
        
        return (current.getElement());
    }

    private BinaryTreeNode<T> findNode(T targetElement, 
                                        BinaryTreeNode<T> next)
    {
        if (next == null)
            return null;
        
        if (next.getElement().equals(targetElement))
            return next;
        
        BinaryTreeNode<T> temp = findNode(targetElement, next.getLeft());
        
        if (temp == null)
            temp = findNode(targetElement, next.getRight());
        
        return temp;
    }

    public String levelOrderTraversal() { // 非递归
        String result = "";
        LinkedQueue<BinaryTreeNode<T>> nodes = new LinkedQueue<>();
        LinkedQueue<T> temp = new LinkedQueue<>();
        BinaryTreeNode<T> current;
        nodes.enqueue(root);

        while(!nodes.isEmpty()) {
            current = nodes.dequeue();
            result += current.element + "\n";

            if (current != null) {
                temp.enqueue(current.getElement());
                if (current.getLeft() != null)
                    nodes.enqueue(current.getLeft());
                if (current.getRight() != null)
                    nodes.enqueue(current.getRight());
            }
            else
                temp.enqueue(null);
        }
        return result;
    }

    private void levelOrder(BinaryTreeNode<T> node, int level) { // 递归
        for (int i = 0; i < level; i ++)
            System.out.print(" ");
        if (node == null || level < 1) {
            return;
        }
        if (level == 1) {
            System.out.print(node.element);
            return;
        }
        levelOrder(node.left, level - 1);
        levelOrder(node.right, level - 1);
    }

    public void levelOrderTra() {
        for (int i = 1; i < getHeight() + 1; i++)
            levelOrder(root, i);
    }

    public String toString() {
        return null;
    }

    public void inOrderTraversal(BinaryTreeNode<T> node) {
        if (node != null) {
            inOrderTraversal(node.left);
            System.out.print(node);
            inOrderTraversal(node.right);
        }

    }

    public void preOrderTraversal(BinaryTreeNode<T> node) {
        if (node != null) {
            System.out.print(node);
            preOrderTraversal(node.left);
            preOrderTraversal(node.right);
        }
    }

    public void postOrderTraversal(BinaryTreeNode<T> node) {
        if (node != null) {
            postOrderTraversal(node.left);
            postOrderTraversal(node.right);
            System.out.print(node);
        }
    }

    @Override
    public Iterator<T> iterator() {
        return iteratorInOrder();
    }

    @Override
    public Iterator<T> iteratorInOrder() {
        return null;
    }

    @Override
    public Iterator<T> iteratorPreOrder() {
        return null;
    }

    @Override
    public Iterator<T> iteratorPostOrder() {
        return null;
    }

    @Override
    public Iterator<T> iteratorLevelOrder() {
        return null;
    }


    protected void inOrder(BinaryTreeNode<T> node, 
                           ArrayUnorderedList<T> tempList) 
    {
        if (node != null)
        {
            inOrder(node.getLeft(), tempList);
            tempList.addToRear(node.getElement());
            inOrder(node.getRight(), tempList);
        }
    }


    private class TreeIterator implements Iterator<T>
    {
        private int expectedModCount;
        private Iterator<T> iter;

        public TreeIterator(Iterator<T> iter)
        {
            this.iter = iter;
            expectedModCount = modCount;
        }

        public boolean hasNext() throws ConcurrentModificationException
        {
            if (!(modCount == expectedModCount))
                throw new ConcurrentModificationException();

            return (iter.hasNext());
        }

        public T next() throws NoSuchElementException
        {
            if (hasNext())
                return (iter.next());
            else
                throw new NoSuchElementException();
        }

        public void remove()
        {
            throw new UnsupportedOperationException();
        }
    }


    public BinaryTreeNode<T> TreeFormer(T[] in, int iS, int iL, T[] pre, int pS, int pL) {
        if(iL < 1){
            return null;
        }
        BinaryTreeNode root;
        T element = pre[pS];
        root=new BinaryTreeNode(element);
        boolean isFound = false;
        int temp;
        for(temp = 0;temp < iL; temp++){
            if(in[iS + temp] == element){
                isFound = true;
                break;
            }
        }
        if(!isFound)
            return root;
        root.setLeft(TreeFormer(in, iS, temp, pre, pS + 1, temp));
        root.setRight(TreeFormer(in, iS + temp + 1, iL - temp - 1, pre, pS + temp + 1, pL - temp - 1));
        return root;
    }

    public void buildTree(T[] in, T[] pre) {
        BinaryTreeNode temp = TreeFormer(in, 0, in.length, pre, 0, pre.length);
        root = temp;

    }


}

